/*
 * LocalSol.cpp
 *
 *  Created on: Jun 2, 2012
 *      Author: hugo
 */

#include "LocalSol.h"

LocalSol::LocalSol(Instance *inst,Solution *sol) {
	instance = inst;
	changed=true;

	nodes = (int*)malloc(sizeof(int)*instance->num_vertex());
	for(long i=0;i<instance->num_vertex();i++){
		nodes[i]=0;
	}

	edges = (int*)malloc(sizeof(int)*instance->num_edge());
	for(long i=0;i<instance->num_edge();i++){
		edges[i]=0;
	}

	for(int i=0;i<sol->size();i++){
		Edge *e = sol->get_edge(i);
		//nodes[e->get_i()]=1;
		//nodes[e->get_j()]=1;
		add_vertex(e->get_i());
		add_vertex(e->get_j());
	}
	compute();
}

LocalSol::LocalSol(Instance *inst) {
	instance = inst;
	changed=true;

	nodes = (int*)malloc(sizeof(int)*instance->num_vertex());
	for(long i=0;i<instance->num_vertex();i++){
		nodes[i]=0;
	}

	edges = (int*)malloc(sizeof(int)*instance->num_edge());
	for(long i=0;i<instance->num_edge();i++){
		edges[i]=0;
	}
}

LocalSol::~LocalSol() {
	free(nodes);
	free(edges);
}

Solution* LocalSol::get_solution(){
	Solution *sol = new Solution(instance);
	for(int i=0;i<instance->num_edge();i++){
		if(has_edge(i)){
			sol->add_edge(instance->get_edge(i));
		}
	}
	for(int i=0;i<instance->num_vertex();i++){
		if(has_vertex(i))
			sol->add_vertex(i);
	}
	return sol;
}

float LocalSol::tmp_add_vertex(int id){
  nodes[id]=1;
  float p_cost = prim(true);
  nodes[id]=0;
  tmp_prim_cost= p_cost;
  return get_cost()-prim_cost+tmp_prim_cost-instance->get_vertex(id)->get_prize();
}

void LocalSol::smart_add_vertex(int id){
  nodes[id]=1;
  edges = tmp_edges;
  cost = cost - prim_cost+tmp_prim_cost-instance->get_vertex(id)->get_prize();
}

void LocalSol::add_vertex(Vertex* v){
	add_vertex(v->get_id());
}
void LocalSol::add_vertex(int id){
	if(!nodes[id]){
		nodes[id]=1;
		changed=true;
	}
}

bool LocalSol::has_connection(int id){
	bool connected=false;
	vector<int> nb = instance->neighborhood(id);
	for(unsigned int i=0;i<nb.size() && !connected;i++)
		if(has_vertex(nb[i]))
			connected=true;
	/*for(int i=0;i<instance->num_vertex() && !connected;i++){
		if(nodes[i]){
			Edge *e = instance->get_edge(i,id);
			if(e!=NULL)
				connected=true;
		}
	}*/
	return connected;
}
Edge* LocalSol::get_connection(int id){
	Edge *best=NULL;
	for(int i=0;i<instance->num_vertex();i++){
		if(nodes[i]){
			Edge *e = instance->get_edge(i,id);
			if(e!=NULL){
				if(best==NULL || e->get_cost()<best->get_cost()){
					best=e;
				}
			}

		}
	}
	return best;
}
void LocalSol::remove_vertex(Vertex* v){
	remove_vertex(v->get_id());
}
void LocalSol::remove_vertex(int id){
	if(nodes[id]){
		nodes[id]=0;
		changed=true;
	}
}
void LocalSol::compute(){
	if(changed){
		changed=false;
		cost=0;
		for(long i=0;i<instance->num_edge();i++){
			edges[i]=0;
		}
		cost = kruskal(false);
		prim_cost = cost;
		
		cost -= prone();
		//cout << "Total: " <<  instance->get_total_prize() <<endl;
		//cout << "Cost: " <<  cost <<endl;
		cost+=instance->get_total_prize();
		float prize=0;
		for(int i=0;i<instance->num_vertex();i++){
			if(nodes[i]){
				prize+=instance->get_vertex(i)->get_prize();
				//cout << instance->get_vertex(i)->get_prize() << "+";
			}
		}
		//cout << endl;
		//cout << "Prize: " <<  prize <<endl;
		cost-=prize;
	}
}

LocalSol* LocalSol::copy_nodes(){
	LocalSol *sol = new LocalSol(instance);
	for(long i=0;i<instance->num_vertex();i++){
		sol->nodes[i]=nodes[i];
	}
	sol->changed = true;
	return sol;
}

LocalSol* LocalSol::copy(){
	LocalSol *sol = new LocalSol(instance);
	for(long i=0;i<instance->num_vertex();i++){
		sol->nodes[i]=nodes[i];
	}

	for(long i=0;i<instance->num_edge();i++){
		sol->edges[i]=edges[i];
	}
	sol->cost=cost;
	sol->changed = changed;
	return sol;
}

void LocalSol::pre_prone(){

}

float LocalSol::prone(){
    float less_cost=0;
    int count=0;
    for(long i=instance->num_vertex()-1;i>=0;i--)
    	count+=nodes[i];
    if(count<=1)return 0;
	for(long i=instance->num_vertex()-1;i>=0;i--){
		if(nodes[i]){
			int degree=0;
			float edge_cost=0;
			int dj=-1;
			int edge_id;
			for(long j=0;j<instance->num_vertex();j++){
				Edge *e = instance->get_edge(i,j);
				if(e!=NULL && edges[e->get_id()]){
					degree++;
					edge_cost+=e->get_cost();
					dj=j;
					edge_id=e->get_id();
				}
			}
			if(degree==1){
				if(edge_cost>instance->get_vertex(i)->get_prize()){
					nodes[i]=0;
					edges[edge_id]=0;
					//cost-=edge_cost;
					less_cost+=edge_cost;
					if(dj>i)
						i=dj+1;
				}
			}else if(degree==0){
				nodes[i]=0;
			}
		}
	}
	return less_cost;
}

float LocalSol::kruskal(){
    float k_cost = kruskal(false);
    k_cost -= prone();
    return k_cost;
}

float LocalSol::kruskal(bool tmp){
	int *tree_v = (int*)malloc(sizeof(int)*instance->num_vertex());
	vector<vector<Edge*> > forest;
	vector<float> forest_cost;
	vector<float> forest_prize;
	int *_edges = (int*)malloc(sizeof(int)*instance->num_edge());
	for(long i=0;i<instance->num_edge();i++){
		_edges[i]=0;
	}
	
	int *_nodes = (int*)malloc(sizeof(int)*instance->num_vertex());
	for(long i=0;i<instance->num_vertex();i++){
		_nodes[i]=0;
	}
	kruskal_prize = 0;
	long k=0;
	for(long i=0;i<instance->num_vertex();i++){
	    if(has_vertex(i)){
		    tree_v[i]=k++;
		    vector<Edge*> tree_e;
		    forest.push_back(tree_e);
		    forest_cost.push_back(0);
		    forest_prize.push_back(instance->get_vertex(i)->get_prize());
		}else{
		    tree_v[i]=-1;
		}
	}
	float cost = 0;
	if(k>0){
	    Edge *best;
	    for(int i=0;i<instance->num_edge();++i){
	        best = instance->get_edge_sorted_by_cost(i);
	        if(tree_v[best->get_i()]==-1 || tree_v[best->get_j()]==-1)continue;
	        if(tree_v[best->get_i()]!=tree_v[best->get_j()]){
	            int from = max(tree_v[best->get_i()],tree_v[best->get_j()]);
	            int to = min(tree_v[best->get_i()],tree_v[best->get_j()]);
	            for(unsigned int j=0;j<forest[from].size();++j){
	                Edge *e = forest[from][j];
	                tree_v[e->get_i()]=to;
	                tree_v[e->get_j()]=to;
	                forest[to].push_back(e);
	            }
	            tree_v[best->get_i()]=to;
                tree_v[best->get_j()]=to;
	            forest[to].push_back(best);
	            forest_cost[to] = forest_cost[to]+forest_cost[from] + best->get_cost();
	            forest_prize[to] = forest_prize[to] + forest_prize[from];
	            forest_prize[from] = -1;
	            forest_cost[from] = -1;
	        }
	    }
	    float best_val;
	    int best_f = -1;
	    for(unsigned int j=0;j<forest.size();++j){
	        float tmp_val = forest_prize[j] - forest_cost[j];
	        if(forest_prize[j]==-1)continue;
            if(best_f==-1 || tmp_val>best_val){
                best_f = j;
                best_val = tmp_val;
            }
	    }
	    for(int i=0;i<instance->num_vertex();++i)
	    	if(tree_v[i]==best_f)
	    		_nodes[i]=1;
	    for(unsigned j=0;j<forest[best_f].size();j++){
            _edges[forest[best_f][j]->get_id()] = 1;
            _nodes[forest[best_f][j]->get_i()]=1;
            _nodes[forest[best_f][j]->get_j()]=1;
	    }
	    cost = forest_cost[best_f];
	    kruskal_prize = forest_prize[best_f];
	}
	
	if(tmp)
	  tmp_edges = _edges;
	else{
	  edges = _edges;
	  nodes = _nodes;
	}
	  
	return cost;
}

int* LocalSol::prim(int *visited, int init_i, float *p_cost, float *prize){
	visited[init_i]=1;
	*prize+= instance->get_vertex(init_i)->get_prize();
	int *_edges = (int*)malloc(sizeof(int)*instance->num_edge());
	for(long i=0;i<instance->num_edge();i++){
		_edges[i]=0;
	}

	*p_cost = 0;
	*prize = 0;
	Edge *best;

	do{
		best=NULL;
		int best_j=-1;
		for(int i=0;i<instance->num_vertex();i++){
			if(nodes[i] && visited[i]){
				for(int j=0;j<instance->num_vertex();j++){
					if(nodes[j] && !visited[j]){
						Edge *e=instance->get_edge(i,j);
						if(e!=NULL){
							if(best==NULL || e->get_cost()<best->get_cost()){
								best=e;
								best_j=j;
							}
						}
					}
				}
			}
		}
		if(best!=NULL){
			visited[best_j]=1;
			*prize+= instance->get_vertex(best_j)->get_prize();
			_edges[best->get_id()]=1;
			(*p_cost)+=best->get_cost();
		}
	}while(best!=NULL);
	return _edges;
}
float LocalSol::prim(){
  return prim(false);
}

float LocalSol::prim(bool tmp){
	float p_cost=0;
	int init_i=-1;
	int *visited = (int*)malloc(sizeof(int)*instance->num_vertex());
	for(long i=0;i<instance->num_vertex();i++){
		visited[i]=0;
	}

	float max_val;
	int *_best_edges;
	int *_edges;
	for(long i=0,count=0;i<instance->num_vertex();i++){
		float tmp_cost;
		float tmp_prize;
		if(!visited[i] && nodes[i]){
			_edges = prim(visited,i,&tmp_cost,&tmp_prize);
			if(count==0 || tmp_prize - tmp_cost > max_val){
				max_val = tmp_prize - tmp_cost;
				p_cost = tmp_cost;
				_best_edges = _edges;
				count++;
			}
		}
	}
	if(tmp)
	  tmp_edges = _best_edges;
	else
	  edges = _best_edges;
	return p_cost;
}

float LocalSol::prim_prize(){
	float p_cost=0;
	int init_i=-1;
	int *visited = (int*)malloc(sizeof(int)*instance->num_vertex());
	for(long i=0;i<instance->num_vertex();i++){
		visited[i]=0;
		if(init_i<0 && nodes[i]){
			init_i = i;
		}
	}
	visited[init_i]=1;
	Edge *best;
	float best_val=0;
	do{
		best=NULL;
		int best_j=-1;
		for(int i=0;i<instance->num_vertex();i++){
			if(nodes[i] && visited[i]){
				for(int j=0;j<instance->num_vertex();j++){
					if(nodes[j] && !visited[j]){
						Edge *e=instance->get_edge(i,j);
						if(e!=NULL){
							//cout << "achou "<< (i+1)<<","<<(j+1)<<endl;
							float val = e->get_cost()-instance->get_vertex(e->get_i())->get_prize() - -instance->get_vertex(e->get_j())->get_prize();
							if(best==NULL || val<best_val){
								best=e;
								best_j=j;
								best_val=val;
							}
						}else{
							//cout << "NAO achou "<< (i+1)<<","<<(j+1)<<endl;
						}
					}
				}
			}
		}
		if(best!=NULL){
			visited[best_j]=1;
			edges[best->get_id()]=1;
			p_cost+=best->get_cost();
		}
	}while(best!=NULL);
	//free(visited);
	return p_cost;
}

float LocalSol::get_cost(){
	if(changed)
		compute();
	return cost;
}
bool LocalSol::has_vertex(Vertex* v){
	return has_vertex(v->get_id());
}
bool LocalSol::has_vertex(int id){
	return nodes[id];
}
bool LocalSol::has_edge(Edge* edge){
	return has_edge(edge->get_id());
}
bool LocalSol::has_edge(int id){
	return edges[id];
}
void LocalSol::print(){
	cout << "LocalSol cost: " << get_cost()<<endl;
	int count=0;
	for(int i=0;i<instance->num_edge();i++){
		if(has_edge(i)){
			Edge *e=instance->get_edge(i);
			cout <<"(" <<e->get_i()+1<<","<<e->get_j()+1 <<") , ";
			count++;
		}
	}
	if(count==0){
		for(int i=0;i<instance->num_vertex();i++){
			if(has_vertex(i))
				cout << (i+1) << ", ";
		}
	}
	cout << endl;
}
